Computer graphics systems are commonly used to display graphical representations of two-dimensional or three-dimensional objects on a two-dimensional display screen. The display screen is typically a cathode ray tube (CRT) device and is divided into arrays of elements referred to as pixels which can be stimulated to emit a range of visual light. The stimulation of the pixels is performed sequentially in some regular order and is repeated typically 50 to 80 times a second in order to maintain a screen image whose intensity does not noticeably change with time.
Typical CRT devices for use with graphics workstations are “raster scan” display devices. Modern raster scan display devices generate images comprising a multiplicity of parallel, non-overlapping bands of pixels comprising sets of parallel lines.
In typical computer graphics systems, an object to be represented on the display screen is broken down into a plurality of graphics primitives. Primitives are the basic components of a graphics picture and may include points, lines, vectors, and polygons, such as triangles. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent a particular view of one or more objects being represented on the screen.
As display systems have increased in complexity to meet an ever-increasing demand for a larger display area and a greater fidelity in the representation of objects on the display screen, the load on the hardware and software required to process the image has also increased. An increase in object representation fidelity has been accomplished, in part, by a decrease in pixel size with a corresponding increase in the number of pixels. The total number of pixels required has also increased as the size of the screen used for display has increased.
To improve performance with the increasing demands upon the rendering system, designers are employing varying techniques to add parallelism in the rendering process. One such technique divides the display's screen space into multiple regions. If a primitive or any portion of a primitive lies within a region, then that region is selected for further processing by a rasterizer that will ultimately render the image contained in that region. Parallelism can now be obtained by having multiple rasterizers available which can be independently assigned to the screen regions that have objects to be rendered, thus allowing multiple objects to be simultaneously rendered.
Typical systems render a straight line segment via a stepping algorithm. A starting point on the display for the line is determined with the pixel corresponding to that point being illuminated. The next pixel to be illuminated is determined by stepping along the major axis one pixel position and then computing the value of the pixel in the minor axis direction. The major axis is defined as that axis to which the line to be rendered forms an included angle of less than or equal to 45 degrees. The minor axis then is the other axis of a Cartesian coordinate system. For example, if the line to be rendered forms an included angle of 37 degrees to the x-axis, then the x-axis is considered to be the major axis and the y-axis the minor axis. In like manner, the next pixel to be illuminated is determined by again stepping one pixel position along the major axis, which is the x-axis in the example, and then computing the corresponding minor axis position, the y-axis in the example, of the pixel on the line to be rendered. This process is repeated until the end of the line is reached. In a region-based rasterizer system, what is desired is a technique that focuses only on the portion of the line within the region currently being processed rather than a traditional technique of starting at the beginning of the line segment and processing to the end, crossing potentially many different regions.